package leetcode_core.leetcode_6;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年02月04日 11:06
 */
public class PostorderTraversal {
    class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode r = null;
        //后续遍历:左右根
        while(root != null || !stack.isEmpty()){
            //先访问左子树
            if(root!=null){
                stack.push(root);
                root = root.left;
            }else{//此时遍历完左子树,然后要访问右子树
                if(root.right!=null && root.right!=r){
                    root = root.right;
                }else{//此时右子树为空,或者是右子树遍历完了
                    //1.遍历节点
                    root = stack.pop();
                    list.add(root.val);
                    //2.维护r指针
                    r = root;
                    //3.维护root指针
                    root = null;
                }
            }
        }
        return list;
    }
}
